\section{\textit{Ant Colony Optimization}}

O algoritmo ACO é baseado no movimento de uma colônia de formigas através 
dos diferentes estados do problema. Este movimento é influenciado por duas 
políticas de decisão local: trilha (trail) e atratividade. Cada formiga 
constrói, incrementalmente, uma solução para o problema. Quando uma formiga 
completa uma solução, ou durante a fase de construção, a formiga avalia a 
solução e modifica o valor trail (trilha) sobre os componentes utilizados 
na sua solução. A informação do feromônio irá direcionar a busca das formigas 
no futuro. Além disso, o algoritmo também inclui mais dois mecanismos: evaporação 
de trilha (trail evaporation) e ações daemon (daemon actions). Evaporação de trilha 
reduz todos os valores da trilha ao longo do tempo, evitando assim qualquer 
possibilidade da solução ficar preso em ótimos locais. As ações daemon são usadas 
para influenciar o processo de busca de uma perspectiva não-local.

O comportamento das formigas ao buscar alimento, a partir da colônia, 
é aleatório. Porém, ao percorrer este caminho, elas deixam um rastro 
de feromônio. Se outras formigas encontram um desses rastros, elas 
tendem a não seguir mais caminhos aleatórios. Em vez disso, seguem a 
trilha encontrada, retornando à colônia, reforçando a quantidade de 
feromônio daquela trilha.

O feromônio evapora com o passar do tempo, reduzindo sua força atrativa. 
Quanto mais formigas passarem por uma trilha, mais tempo será necessário 
para o feromônio evaporar. Este comportamento é vantajoso para evitar a 
convergência para uma solução local ótima. Caso ele não ocorre-se, todas 
as trilhas escolhidas pelas primeiras formigas seriam excessivamente 
atrativas para as outras e, neste caso, a exploração do espaço de solução 
diminuiria consideravelmente.

Como as formigas completam mais rápido um caminho mais curto, a densidade 
do ferômonio destas trilhas aumenta antes que ele comece a evaporar. Quando 
uma formiga encontra um bom (curto) caminho entre a colônia e a fonte de 
alimento, outras formigas tenderão a seguir este caminho, gerando assim 
feedback positivo, o que eventualmente torna um determinado caminho mais 
interessante. A idéia do algoritmo da colônia de formigas é imitar este 
comportamento através de ``formigas virtuais'' que caminham por um grafo que 
por sua vez representa o problema a ser resolvido.